package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
统一方法
 */
public class Of20210304QueryTreeByIteration {

    public static void main(String[] args) {
        System.out.println(postorderTraversal(new TreeNode(1, new TreeNode(2, new TreeNode(4)
                , new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)))));
    }

    /**
     * 迭代法中序遍历
     */
    private static List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        if (root != null) stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if (node != null) {
                stack.pop();// 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right != null) stack.push(node.right);  // 添加右节点（空节点不入栈）
                stack.push(node); // 添加中节点
                stack.push(null);// 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.left!=null) stack.push(node.left);    // 添加左节点（空节点不入栈）
            }else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                stack.pop(); // 将空节点弹出
                node = stack.pop();    // 重新取出栈中元素
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }

    /*
    迭代法前序遍历 :「注意此时我们和中序遍历相比仅仅改变了两行代码的顺序」
     */
    private static List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> result = new ArrayList<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node!=null){
                if (node.right!=null) stack.push(node.right);
                if (node.left!=null) stack.push(node.left);
                stack.push(node);
                stack.push(null);
            }else {
                node = stack.pop();
                result.add(node.val);
            }
        }
        return result;
    }

    /*
    后续遍历代码如下：(「注意此时我们和中序遍历相比仅仅改变了两行代码的顺序」)
     */
    private static List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> result = new ArrayList<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node!=null){
                stack.push(node);
                stack.push(null);
                if (node.right!=null) stack.push(node.right);
                if (node.left!=null) stack.push(node.left);
            }else {
                node = stack.pop();
                result.add(node.val);
            }
        }
        return result;
    }
}
